package middle;

public class Solution_33 {

    public int search(int[] nums, int target) {
        int begin = 0, end = nums.length-1;
        while (true) {
            if (begin+1 >= end) {
                if (nums[begin] == target) {
                    return begin;
                } else if (nums[end] == target) {
                    return end;
                }
                return -1;
            }
            // 至少有一边是有序的
            int middle = (begin + end) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[begin] < nums[middle]) {
                // 左边有序
                if (target < nums[middle] && target >= nums[begin]) {
                    // 目标值在左边
                    end = middle - 1;
                } else {
                    // 目标值在右边
                    begin = middle + 1;
                }
            } else if (nums[middle] < nums[end]) {
                // 右边有序
                if (target > nums[middle] && target <=nums[end]) {
                    // 目标值在右边
                    begin = middle + 1;
                } else {
                    // 目标值在左变
                    end = middle - 1;
                }
            }
        }
    }

    private int search(int[] nums) {
        int begin = 0, end = nums.length-1;
        while (true) {
            if (begin+1 == end) {
                if (nums[end] > nums[begin]) {
                    return begin;
                }
                return end;
            }
            int middle = (begin + end) / 2;
            if (nums[begin] > nums[middle]) {
                end = middle;
            } else {
                end = middle;
            }
        }
    }

    public static void main(String[] args) {
        Solution_33 model = new Solution_33();
        System.out.println(model.search(new int[]{5, 1, 3}, 3));
        System.out.println(model.search(new int[]{4,5,6,7,0,1,2}, 0));
        System.out.println(model.search(new int[]{4,5,6,0,1,2}, 3));
        System.out.println(model.search(new int[]{4,0,1,2}, 0));
        System.out.println(model.search(new int[]{0,1,2}, 2));
        System.out.println(model.search(new int[]{0,1,2,3}, 0));
        System.out.println(model.search(new int[]{0, 1}, 1));
        System.out.println(model.search(new int[]{3}, 1));
        System.out.println(model.search(new int[]{3}, 3));
    }
}
